//题目:
// 给定一个经过编码的字符串，返回它解码后的字符串。
// 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
// 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
// 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<limits.h>
#include<stack>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:
    string decodeString(string s) 
    {
        string ret;//存放返回结果
        stack<char> st;//对s进行入栈操作
        //1.遍历s,对s中的字符进行入栈操作
        for(const auto& ch:s)
        {
            if(ch!=']') st.push(ch);
            else //ch=']'
            {
                //1.对st出栈操作,找到对应[]内的字符串,直到遇到数字字符为止,将其放入tmp中
                string tmp;
                while(!st.empty() && (st.top()<'0' || st.top()>'9'))
                {
                    if(st.top()!='[')
                        tmp+=st.top();
                    st.pop();
                }
                //2.由于出栈时,tmp内的字符串与原序是反的，所以需要对其逆序
                if(tmp.size()>1) reverse(tmp.begin(),tmp.end());
                //3.此时st.top()存放的就是tmp的个数?[tmp],但?可能不止一位
                int count=0,i=1;
                while(!st.empty() && st.top()>='0' && st.top()<='9')
                {
                    count+=(st.top()-'0')*i;
                    i*=10;
                    st.pop();
                }
                //4.将count个tmp字符串中的字符push到st中
                for(int i=0;i<count;i++)
                    for(int j=0;j<tmp.size();j++)
                        st.push(tmp[j]);
            }
        }
        //2.将st中的字母出栈
        while(!st.empty())
        {
            ret+=st.top();
            st.pop();
        }
        //3.将结果逆序
        reverse(ret.begin(),ret.end());
        return ret;
    }
};